package com.hjx.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 4. 寻找两个有序数组的中位数
 *
 * 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
 *
 * 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
 *
 * 你可以假设 nums1 和 nums2 不会同时为空。
 *
 * 示例 1:
 *
 * nums1 = [1, 3]
 * nums2 = [2]
 *
 * 则中位数是 2.0
 * 示例 2:
 *
 * nums1 = [1, 2]
 * nums2 = [3, 4]
 *
 * 则中位数是 (2 + 3)/2 = 2.5
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode_4 {


    /**
     * 归并操作的工作原理如下：
     * 第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
     * 第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
     * 第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
     * 重复步骤3直到某一指针超出序列尾
     * 将另一序列剩下的所有元素直接复制到合并序列尾
     *
     * @param a
     * @param b
     * @return
     */
    public double findMedianSortedArrays(int[] a, int[] b){

        int len = a.length + b.length;

        int[] mergeNums = new int[len];
        boolean flag = false;
        for(int i = 0, j = 0, k = 0; k < len; k++){

            if(!flag && a[i] <= b[j]){
                mergeNums[k] = a[i];
                if (i == a.length - 1){
                    flag = true;
                }
                if (i != a.length - 1) {
                    i++;
                }

            } else {
                mergeNums[k] = b[j];
                if (j != b.length - 1){
                    j++;
                }

            }

        }
        double mid = 0;
        if (len % 2 == 0 ){
            mid = (double)(mergeNums[len / 2 - 1] + mergeNums [len / 2]) / 2d;

        } else {
            mid = mergeNums[len / 2];
        }

        return mid;
    }

    /**
     * 笨办法
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays1(int[] nums1, int[] nums2) {

        /*
         问题一：什么是中位数？
          答：中位数（Median）又称中值，统计学中的专有名词，是按顺序排列的一组数据中居于中间位置的数，
          代表一个样本、种群或概率分布中的一个数值，其可将数值集合划分为相等的上下两部分。
          对于有限的数集，可以通过把所有观察值高低排序后找出正中间的一个作为中位数。
          如果观察值有偶数个，通常取最中间的两个数值的平均数作为中位数。
         */
        /*
         * 根据中位数的定义可知最笨的方法为两数组合并排序得到新数组，然后求中位数
         */
        int len = nums1.length + nums2.length;
//        int[] mergeNums = new int[len];

        List<Integer> list1 = Arrays.stream(nums1).boxed().collect(Collectors.toList());
        List<Integer> list2 = Arrays.stream(nums2).boxed().collect(Collectors.toList());
//        int maxLen = nums1.length >= nums2.length ? nums1.length : nums2.length;
//        //重新排序数组
//        for (int n = maxLen-1; n > 0 ; n--){
//
//        }
        List<Integer> list3 = new ArrayList<>();
        list3.addAll(list2);
        list3.addAll(list1);
        List<Integer> list4 = list3.stream().sorted().collect(Collectors.toList());
        Integer[] mergeNums = list4.toArray(new Integer[len]);

        double mid = 0;
        if (len % 2 == 0 ){
            mid = (double)(mergeNums[len / 2 - 1] + mergeNums [len / 2]) / 2d;

        } else {
            mid = mergeNums[len / 2];
        }

        return mid;
    }
}
